#ifndef __SCAN_H__
#define __SCAN_H__

#include <cstdlib>
#include <iostream>
#include <pthread.h>
#include <assert.h>
#include <cstdio>
#include "global.h"

using namespace std;

template <typename D, typename T>
class Scanner {
public:
  D* data;
  D* result;

  T nodeval[99];
  T ltally[99];

  INDEX length;

  int threadid[99];
  pthread_t threads[99];

  Scanner(D*, D*, INDEX);
  void Start();
  void* Scan(void*);
  virtual T init() = 0;
  virtual T accum(T, D) = 0;
  virtual T combine(T, T) = 0;
  virtual T scan(T, D) = 0;

  static void* ScanWrapper(void* pt_pair) {
    return ((Scanner<D, T>*) ((PtPair*)pt_pair)->This)->Scan(((PtPair*)pt_pair)->threadid);
    // Pthread requires static function without "this" pointer
    // But functions called by Scan needs this
    // Using method mentioned here to get around:
    // http://stackoverflow.com/questions/1151582/pthread-function-from-a-class
    // Answered by Jeremy Friesner
  }
};

template <typename D, typename T>
Scanner<D, T>::Scanner(D* _data, D* _result, INDEX _length) {
  data = _data;
  result = _result;
  length = _length;
  assert(_length % P == 0);

  for(int i=0; i<P; i++)
    threadid[i] = i;

  pthread_mutex_init(&lock, NULL);
  pthread_barrier_init(&barrier, NULL, P);
}

template <typename D, typename T>
void Scanner<D, T>::Start() {
  int rc;
  PtPair pt_pair[99];

  for(int i=0; i<P; i++) {
    pt_pair[i].This = this;
    pt_pair[i].threadid = (void*)(threadid+i);

    rc = pthread_create(&threads[i], NULL, ScanWrapper, (void*)(&pt_pair[i]));
    if (rc)
      exit(-1);
  }
  for(int i=0; i<P; i++) {
    rc = pthread_join(threads[i], NULL);
  }

 // for(INDEX i=0; i<length; i++)
 //   cout<<result[i]<<" ";
 // cout<<endl;
  return;
}

template <typename D, typename T>
void* Scanner<D, T>::Scan(void* threadid_pt) {
  int threadid = *(int*)threadid_pt;
  INDEX base = length/P * threadid;
  INDEX size = length/P;
  T myTally;
  T pTally;
  int stride = 1;

  // local accumulation
  myTally = init();
  for(INDEX i=0; i<size; i++)
    myTally = accum(myTally, data[base+i]);
  nodeval[threadid] = myTally;

  //pthread_mutex_lock (&lock);
  //cout<<"thread: "<<threadid<<" tally: "<<myTally<<endl;
  //pthread_mutex_unlock (&lock);

  // for each stride (except for the last one),
  // store the local accumulation result into ltally array
  // on the next (right-hand-side) index
  while(stride < P) {
    pthread_barrier_wait(&barrier);
    if (threadid%(2*stride) == 0) {
      ltally[threadid+stride] = nodeval[threadid];
      nodeval[threadid] = combine(nodeval[threadid], nodeval[threadid+stride]);
    }
    stride = 2*stride;
  }

  // clear the first local result
  if (threadid == 0) {
    nodeval[0] = init();
  }

  //propogate parent value through the tree to the leaf nodes
  stride = P/2;
  while (stride >= 1) {
    pthread_barrier_wait(&barrier);
    if (threadid%(2*stride) == 0) {
      nodeval[threadid+stride] = combine(nodeval[threadid], ltally[threadid+stride]);
    }
    stride = stride/2;
  }

  pthread_barrier_wait(&barrier);
  pTally = nodeval[threadid];
  for(INDEX i=0; i<size; i++) {
    pTally=accum(pTally, data[i+base]);
    result[i+base] = scan(pTally, data[i+base]);
  }

  //pthread_mutex_lock (&lock);
  //cout<<"finishing thread: "<<threadid<<endl;
  //pthread_mutex_unlock (&lock);

  return NULL;
}

#endif

